package mo.tags.stack;

import mo.common.ListNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class L1019 {

    public int[] nextLargerNodes(ListNode head) {
        ListNode cur = head;
        List<Integer> larger = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        int idx = 0;
        while (cur != null) {
            int val = cur.val;
            while (!stack.isEmpty() && larger.get(stack.peek()) < val) {
                larger.set(stack.pop(), val);
            }
            stack.push(idx);
            larger.add(val);
            cur = cur.next;
            idx++;
        }
        while (!stack.isEmpty()) {
            larger.set(stack.pop(), 0);
        }
        return larger.stream().mapToInt(Integer::intValue).toArray();
    }

}
